package com.sx.sx1.lintcode.day717;

import java.util.Stack;

public class LC122 {
    static class Solution {
        /**
         * @param heights: A list of integer
         * @return: The area of largest rectangle in the histogram
         */
        public int largestRectangleArea(int[] heights) {
            //https://blog.csdn.net/ljyljyok/article/details/78127898
            if(heights ==null || heights.length ==0)
                return 0;

            //为方便计算横向距离width，存入栈中的是height[]各个元素的索引，而非值！
            Stack<Integer> s = new Stack<>();
            int ans =0;
            for (int i = 0; i <=heights.length ; i++) {
                //当遍历到最后一个元素时，i为height.length，已经跑出了height[]数组。
                //trick：此时,为保证数组最后一个元素的最大矩形面积也被计算，
                // 增加height[height.length] = -1
                int cur = (i==heights.length?-1: heights[i]);//此句勿漏！！！
                while (!s.isEmpty() && cur<= heights[s.peek()]){
                    //非if-clause!!!
                    int h = heights[s.pop()];
                    int w=s.isEmpty()?i:i-s.peek()-1;
                    int curans = h*w;
                    if(curans> ans)
                        ans= curans;
                }
                s.add(i);
            }
            return ans;
        }
    }


    public static void main(String[] args) {
        Solution obj = new Solution();
        System.out.println(obj.largestRectangleArea(new int[]{2,1,5,6,2,3}));
        System.out.println(obj.largestRectangleArea(new int[]{1,1}));
    }
}


/*
LintCode-Logo
学习
刷题
内推
VIP
其他...
搜索题目、标签、题集
邀请有礼
中文
您上个月的个人报告已生成，点击查看
avatar
122 · 直方图最大矩形覆盖
算法
困难
通过率
35%

题目
题解34
笔记
讨论99+
排名
记录
描述
给出的n个非负整数表示每个直方图的高度，每个直方图的宽均为1，在直方图中找到最大的矩形面积。

样例
样例 1：

输入：

height = [2,1,5,6,2,3]
输出：

10
解释：

第三个和第四个直方图截取矩形面积为2*5=10。

样例 2：

输入：

height = [1,1]
输出：

2
解释：

第一个和第二个直方图截取矩形面积为2*1=2。

相关知识
学习《算法——双指针思想》课程中的3.7更广泛的“双指针”——单调堆栈相关内容 ，了解更多相关知识！
标签
相关题目

126
最大树
困难

510
最大矩形
困难
推荐课程

春招算法高频题冲刺班
精准押题，抱佛脚突击算法面试，最近6个月新题/难题/高频题全覆盖！
121/3325
已开启智能提示
发起考试
45 分 00 秒
123456789

控制台
        历史提交

 */
